import java.util.*;


public abstract class ADTHeap<Tipo> {
	protected Vector<Tipo> info;
	protected Comparator<Tipo> comp;
	
	public ADTHeap(Comparator<Tipo> comp){
		info = new Vector<Tipo>();
		this.comp = comp;
	}
	
	public int padre(int i){
		return (i-1)/2;
	}
	
	public int izquierda(int i){
		return 2*i+1;
	}

	public int derecha(int i){
		return 2*(i+1);
	}
	
	public void filtrar(int hoja){
		int padre = padre(hoja);
		Tipo valor = info.get(hoja);
		while (hoja > 0 && (comp.compare(valor, info.get(padre)) < 0)){
			info.set(hoja, info.get(padre));
			hoja = padre;
			padre = padre(hoja);
		}
		info.set(hoja, valor);		
	}
	
	public void add(Tipo valor){
		info.add(valor);
		filtrar(info.size()-1);
	}
	
	public void bajarRaiz(int raiz){
		int tamano = info.size();
		Tipo valor = info.get(raiz);
		while(raiz < tamano){
			int posHijo = izquierda(raiz);
			if (posHijo < tamano){
				if ((derecha(raiz) < tamano) && 
						(comp.compare(info.get(posHijo+1),
								info.get(posHijo)) < 0)){
					posHijo++;
				}
				if (comp.compare(info.get(posHijo), valor) < 0){
					info.set(raiz, info.get(posHijo));
					raiz = posHijo;
				}
				else{
					info.set(raiz, valor);
					return;
				}
			}
			else{
				info.set(raiz, valor);
				return;
			}
		}
	}	
	
	public Tipo remove(){
		try{
			Tipo valMin = getFirst();
			info.set(0, info.get(info.size()-1));
			info.setSize(info.size()-1);
			if (info.size() > 1)
				bajarRaiz(0);
			return valMin;
		}
		catch(Exception e){
			return null;
		}
	}
	
	public Tipo getFirst(){
		return info.get(0);
	}
	
	
	public int size(){
		return info.size();
	}
	
	public boolean isEmpty(){
		if (size() == 0){
			return true;
		}
		return false;
	}
	
	public void clear(){
		info.clear();
	}
}
